home *** CD-ROM | disk | FTP | other *** search
/ BCI NET 2 / BCI NET 2.iso / archives / programming / source / graphicgems4.lha / GemsIV / delaunay / quadedge.h < prev    next >
Encoding:
C/C++ Source or Header  |  1995-02-06  |  3.3 KB  |  171 lines

  1. #ifndef QUADEDGE_H
  2. #define QUADEDGE_H
  3.  
  4. #include <geom2d.h>
  5.  
  6. class QuadEdge;
  7.  
  8. class Edge {
  9.     friend QuadEdge;
  10.     friend void Splice(Edge*, Edge*);
  11.   private:
  12.     int num;
  13.     Edge *next;
  14.     Point2d *data;
  15.   public:
  16.     Edge()            { data = 0; }
  17.     Edge* Rot();
  18.     Edge* invRot();
  19.     Edge* Sym();
  20.     Edge* Onext();
  21.     Edge* Oprev();
  22.     Edge* Dnext();
  23.     Edge* Dprev();
  24.     Edge* Lnext();
  25.     Edge* Lprev();
  26.     Edge* Rnext();
  27.     Edge* Rprev();
  28.     Point2d* Org();
  29.     Point2d* Dest();
  30.     const Point2d& Org2d() const;
  31.     const Point2d& Dest2d() const;
  32.     void  EndPoints(Point2d*, Point2d*);
  33.     QuadEdge* Qedge()    { return (QuadEdge *)(this - num); }
  34.     void Draw(unsigned int);
  35. };
  36.  
  37. class QuadEdge {
  38.     friend Edge *MakeEdge();
  39.   private:
  40.     Edge e[4];
  41.     unsigned int ts;
  42.   public:
  43.     QuadEdge();
  44.     int TimeStamp(unsigned int);
  45. };
  46.  
  47. class Subdivision {
  48.   private:
  49.     Edge *startingEdge;
  50.     Edge *Locate(const Point2d&);
  51.   public:
  52.     Subdivision(const Point2d&, const Point2d&, const Point2d&);
  53.     void InsertSite(const Point2d&);
  54.     void Draw();
  55. };
  56.  
  57. inline QuadEdge::QuadEdge()
  58. {
  59.     e[0].num = 0, e[1].num = 1, e[2].num = 2, e[3].num = 3;
  60.     e[0].next = &(e[0]); e[1].next = &(e[3]);
  61.     e[2].next = &(e[2]); e[3].next = &(e[1]);
  62.     ts = 0;
  63. }
  64.  
  65. inline int QuadEdge::TimeStamp(unsigned int stamp)
  66. {
  67.     if (ts != stamp) {
  68.         ts = stamp;
  69.         return TRUE;
  70.     } else
  71.         return FALSE;
  72. }
  73.  
  74. /************************* Edge Algebra *************************************/
  75.  
  76. inline Edge* Edge::Rot()
  77. // Return the dual of the current edge, directed from its right to its left.
  78. {
  79.     return (num < 3) ? this + 1 : this - 3;
  80. }
  81.  
  82. inline Edge* Edge::invRot()
  83. // Return the dual of the current edge, directed from its left to its right.
  84. {
  85.     return (num > 0) ? this - 1 : this + 3;
  86. }
  87.  
  88. inline Edge* Edge::Sym()
  89. // Return the edge from the destination to the origin of the current edge.
  90. {
  91.     return (num < 2) ? this + 2 : this - 2;
  92. }
  93.  
  94. inline Edge* Edge::Onext()
  95. // Return the next ccw edge around (from) the origin of the current edge.
  96. {
  97.     return next;
  98. }
  99.  
  100. inline Edge* Edge::Oprev()
  101. // Return the next cw edge around (from) the origin of the current edge.
  102. {
  103.     return Rot()->Onext()->Rot();
  104. }
  105.  
  106. inline Edge* Edge::Dnext()
  107. // Return the next ccw edge around (into) the destination of the current edge.
  108. {
  109.     return Sym()->Onext()->Sym();
  110. }
  111.  
  112. inline Edge* Edge::Dprev()
  113. // Return the next cw edge around (into) the destination of the current edge.
  114. {
  115.     return invRot()->Onext()->invRot();
  116. }
  117.  
  118. inline Edge* Edge::Lnext()
  119. // Return the ccw edge around the left face following the current edge.
  120. {
  121.     return invRot()->Onext()->Rot();
  122. }
  123.  
  124. inline Edge* Edge::Lprev()
  125. // Return the ccw edge around the left face before the current edge.
  126. {
  127.     return Onext()->Sym();
  128. }
  129.  
  130. inline Edge* Edge::Rnext()
  131. // Return the edge around the right face ccw following the current edge.
  132. {
  133.     return Rot()->Onext()->invRot();
  134. }
  135.  
  136. inline Edge* Edge::Rprev()
  137. // Return the edge around the right face ccw before the current edge.
  138. {
  139.     return Sym()->Onext();
  140. }
  141.  
  142. /************** Access to data pointers *************************************/
  143.  
  144. inline Point2d* Edge::Org()
  145. {
  146.     return data;
  147. }
  148.  
  149. inline Point2d* Edge::Dest()
  150. {
  151.     return Sym()->data;
  152. }
  153.  
  154. inline const Point2d& Edge::Org2d() const
  155. {
  156.     return *data;
  157. }
  158.  
  159. inline const Point2d& Edge::Dest2d() const
  160. {
  161.     return (num < 2) ? *((this + 2)->data) : *((this - 2)->data);
  162. }
  163.  
  164. inline void Edge::EndPoints(Point2d* or, Point2d* de)
  165. {
  166.     data = or;
  167.     Sym()->data = de;
  168. }
  169.  
  170. #endif /* QUADEDGE_H */
  171.